package net.cloudsun.graph.core;

import java.util.*;

/**
 * 无权重图
 *
 * @author Ryan
 * @since 1.0
 */
public class UnweightedGraph<E> {

    /**
     * 节点
     */
    protected E[] vertices;
    /**
     * 边
     */
    protected List<? extends UnweightedEdge> [] edges;

    public UnweightedGraph() {
    }

    public List<E> bfs(int first, int finalState) {
        // 宽度搜索。直接一个Deque
        HashMap<Integer,Integer> parentMap = new HashMap<>();
        HashSet<Integer> visited = new HashSet<>();

        Queue<Integer> deque = new LinkedList<>();
        deque.offer(first);

        Integer e = null;
        while (!Objects.equals(e, finalState) && !deque.isEmpty()) {
            e = deque.poll();
            visited.add(e);
            List<? extends Edge> edgeList = this.edges[e];
            for (Edge edge : edgeList) {
                // 这里决定parent
                if (!visited.contains(edge.getTo())) {
                    parentMap.put(edge.getTo(), edge.getFrom());
                    deque.add(edge.getTo());
                }
            }
        }
        List<E> path = new ArrayList<>();
        if (Objects.equals(e, finalState)) {
            for (Integer i = e; i != null; i = parentMap.get(i)) {
                E vertex = vertices[i];
                path.add(vertex);
            }
        }

        visited.clear();
        parentMap.clear();
        return path;
    }

    public Set<Integer> bfs(int first) {
        // 宽度搜索。直接一个Deque
        HashMap<Integer,Integer> parentMap = new HashMap<>();
        HashSet<Integer> visited = new HashSet<>();

        Deque<Integer> deque = new LinkedList<>();
        deque.offer(first);

        Integer e;
        while (!deque.isEmpty()) {
            e = deque.pollFirst();
            visited.add(e);
            List<? extends Edge> edgeList = this.edges[e];
            for (Edge edge : edgeList) {
                // 这里决定parent
                if (!visited.contains(edge.getTo())) {
                    parentMap.put(edge.getTo(), edge.getFrom());
                    deque.offerLast(edge.getTo());
                }
            }
        }

        return visited;
    }

    public E[] getVertices() {
        return vertices;
    }

    public List<? extends Edge>[] getEdges() {
        return edges;
    }
}
